This invention relates to the routing of traffic on communication networks of the kind known as ring networks. More particularly, the invention relates to ring networks that support multiple channels, such as multiple wavelength channels, and to routing methods that seek efficient use of a fixed number of such channels.
FIG. 1 depicts, in schematic fashion, a typical ring network including nodes 10.1-10.6, clockwise links 15.1-15.6, and counterclockwise links 20.1-20.6. (The physical medium, such as an optical fiber, that embodies a link may carry signals bidirectionally. However, for convenience in the following discussion, it is helpful to represent even bidirectional links as pairs of directed links. A network that can be described in this manner is referred to as a xe2x80x9cdirected ring network.xe2x80x9d) A route or connection is a contiguous sequence of links leading from an initial node to a terminal node. For example, route 25 of FIG. 1 is a clockwise route from node 10.2 to node 10.4.
Ring networks have the well-known advantage that when an accident or malfunction causes a link to be cut, thus interrupting traffic, the interrupted traffic can often be carried over alternative routes having the opposite circulatory direction. (I.e., clockwise-routed traffic is re-routed counterclockwise, or vice versa.) As a consequence, practitioners in the field of communication network architecture have regarded ring networks as attractive for many applications.
For any given routing and any given directed link of a ring network, we use the term link load to refer to the number of connections routed through the given link. We use the term ring load to refer to the maximum link load (in either circulatory direction) over the entire network.
It is typical for the links of a ring network to have some maximum capacity; that is, an upper limit on the number of routed demands that can pass through a given link in a given direction. In order to make efficient use of such a ring network, it is advantageous to route the demands in such a way that the ring load is kept as low as possible. Otherwise, there is a danger that some link will too soon reach its maximum capacity, so that no further routing can be made through that link.
Thus, there is a need for a procedure that optimally routes a given set of demands; that is, a procedure that achieves a routing having the minimum possible ring load. Moreover, it is desirable for such a routing to be achievable within a computational time period short enough for practical use in handling real-time traffic. As a general rule, this means that the computational time should be less than an exponential function of the network size.
By way of example, if an optimal routing were computed by exhaustive search and the number of nodes in the network were on the order of fifty or more, the time required for the computation would be prohibitive in applications directed to handling real-time traffic.
Until now, there has been no known procedure for solving the optimal routing problem on a ring network within less than exponential time.
In some types of ring networks, a fixed number of multiple channels are available for carrying signals on each link. These channels may be embodied in various ways, including respective optical fibers, respective electrical conductors, or respective wavelengths of light. For purposes of illustration, we will now discuss optical WDM ring networks, in which each link comprises multiple wavelength channels. However, it should be noted that the principles to be discussed apply generally to other multiple-channel ring networks.
To establish a logical connection between nodes in such a network, an administrative entity first chooses a route, and then it assigns a wavelength to the connection for each link in the route. The network is referred to as wavelength selective (WS) if all of these assigned wavelengths are the same (for the given connection), and wavelength interchanging (WI) if different links (for the given connection) may be assigned different wavelengths. In a WI network, a device which we refer to as a wavelength translator would typically be available at the various nodes to intercept incoming signals on one set of respective wavelengths and re-transmit them, as outgoing signals, on a different set of respective wavelengths.
WS networks will generally be less expensive than WI networks of the same size, because they do not require wavelength translators. However, if the number of available wavelengths is fixed, the WI network will generally have more capacity, because it can reuse the same wavelength on two or more overlapping routes (although of course not on overlapping links). As a consequence, adding a new connection does not necessarily result in utilizing a new wavelength, even if the new route overlaps all of the previously established routes.
Thus, in practice, there will be a tradeoff between the cost advantages of the WS network and the capacity advantages of the WI network.
In WDM ring networks of both kinds, it is advantageous to carry out the task of wavelength assignment (in a general context, this may be thought of as xe2x80x9cchannelxe2x80x9d assignment) using as few wavelengths (or xe2x80x9cchannelsxe2x80x9d) as possible. If the total number of available wavelength channels is limited, this assures that the capacity of the network is being used efficiently. If the least possible number of wavelengths is used, we say that the wavelength assignment is optimal.
In WI networks, given a particular route set, optimal wavelength assignment is readily carried out in less than exponential time, provided enough nodes are equipped with wavelength translators. A practical method for optimal routing is advantageous in this context because it can be used to minimize (over all possible route sets) the number of wavelengths needed.
In WS networks, the problem of optimal wavelength assignment (for a given route set) is an NP-complete problem. In other words, there is no known way to carry out such an assignment in less than exponential time, and it is extremely unlikely that any procedure for doing so will ever be found.
Under these circumstances, it is highly advantageous to have a wavelength-assignment procedure that can perform, with some performance guarantee, within a practical period of time, such as polynomial time. In general, as the estimated cost (according to the performance guarantee) goes down, the procedure becomes more useful, because it will appear cost-effective to apply it to a wider range of practical problems. A practical method for optimal routing is advantageous in this context because if a wavelength-assignment procedure has a performace guarantee (for a given route set), optimal routing can be used to minimize the estimated cost over all possible route sets. By making the estimated cost as small as possible, the utility of the wavelength-assignment procedure is enhanced.
We have invented a routing procedure, for directed ring networks, that achieves optimal routing in polynomial time.
When our routing procedure is combined with an appropriate procedure for optimally assigning wavelength channels in WI networks, wavelengths can be assigned in a manner that is optimal over all possible route sets.
When our routing procedure is combined with an appropriate procedure for assigning wavelength channels in WS networks, wavelengths can be assigned, in polynomial time, with a performance guarantee. This guarantee is that the total number of wavelengths used will be no more than twice the ring load obtained by optimal routing, less one.
In one aspect, the invention involves a method for routing a set of demands in a ring network that comprises nodes interconnected by directed links, in which each demand may be routed clockwise or counterclockwise.
According to our method, a linear program is solved to obtain a set of routing variables that minimize an objective function. Each routing variable corresponds to a respective one of the demands, and has a value that falls on a closed interval between endpoints such as the values 0 and 1. A value falling at one of the endpoints signifies clockwise routing, and a value falling at the other signifies counterclockwise routing.
A load of at least one kind is associated with each link of the network. The objective function describes the value of this load maximized over all links of the network, so that a solution of the linear program provides a minimum value of the maximized load.
The method further comprises rounding the routing variables so that the value of each routing variable falls at one of the endpoints. This rounding is carried out such that the maximized load does not exceed the previously-obtained minimum value of the maximized load. The method further comprises routing each of the demands clockwise or counterclockwise, in accordance with the value of its respective routing variable.
In applications to WDM rings, some aspects of the inventive method further involve steps directed to the assignment of wavelength channels. In particular embodiments, the ring network is represented as a pair of directed linear networks, in each of which one node of the ring network is represented as two respective image nodes situated at opposite ends of the linear network. At most L wavelengths are assigned to each of the linear networks, wherein L is equal to the minimum value of the maximized load, as obtained by the routing procedure described above. When the ends of each linear network are rejoined to restore the ring network, no more than Lxe2x88x921 additional wavelengths need to be assigned.